package com.algorithm.btree;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class BTree<K extends Comparable<K>, V> {
	int degree;// 度数
	Node<K, V> root;// 根节点
	boolean allowDup = true;

	// 读写锁
	ReentrantReadWriteLock rwl = new ReentrantReadWriteLock(true);
	final Lock rl = rwl.readLock();
	final Lock wl = rwl.writeLock();

	/**
	 * 构造函数
	 * 
	 * @param degree
	 *            最小度数
	 */
	public BTree(int degree) {
		this(degree, true);
	}

	/**
	 * 构造函数
	 * 
	 * @param degree
	 *            最小度数
	 * @param dup
	 *            允许key重复
	 */
	public BTree(int degree, boolean dup) {
		this.degree = degree;
		root = new Node<K, V>(degree);
		root.leaf = true;
		root.len = 0;
		allowDup = dup;
	}

	/**
	 * 匹配Key 返回第一条結果
	 * 
	 * @param key
	 * @return
	 */
	public V find(K key) {
		rl.lock();
		Entry<K, V> entry = findEntry(key, true);
		rl.unlock();
		if (entry != null) {
			return entry.value;
		}
		return null;
	}

	/**
	 * 匹配key，返回所有记录
	 * 
	 * @param key
	 * @return
	 */
	public List<V> findAll(K key) {
		List<V> result = new ArrayList<V>();
		rl.lock();
		List<Entry<K, V>> entryList = findEntry(key, key, 0, 0, true);
		rl.unlock();
		for (Entry<K, V> entry : entryList) {
			result.add(entry.value);
		}
		return result;
	}

	/**
	 * 范围匹配Key in [min,max]，返回所有记录
	 * 
	 * @param min
	 * @param max
	 * @param offset
	 * @param limit
	 * @return
	 */
	public List<V> findAll(K min, K max, int offset, int limit) {
		List<V> result = new ArrayList<V>();
		rl.lock();
		List<Entry<K, V>> entryList = findEntry(min, max, offset, limit, true);
		rl.unlock();
		for (Entry<K, V> entry : entryList) {
			result.add(entry.value);
		}
		return result;
	}

	/**
	 * 插入记录
	 * 
	 * @param key
	 * @param value
	 */
	public void insert(K k, V v) {
		wl.lock();
		_insert(k, v);
		wl.unlock();
	}

	/**
	 * 插入记录
	 * 
	 * @param key
	 * @param value
	 */
	public void _insert(K k, V v) {
		if (!allowDup) {
			if (existsEntry(k)) {
				wl.unlock();
				return;
			}
		}

		Node<K, V> node = root;
		// 如果跟节点为满节点
		if (node.full()) {
			Node<K, V> newNode = allocNode();
			root = newNode;
			newNode.len = 0;
			newNode.setChild(0, node);
			newNode.leaf = false;
			split(newNode, 0, node);
			insert(newNode, k, v);
		} else {
			insert(node, k, v);
		}
	}

	/**
	 * 匹配key 更新所有记录value
	 * 
	 * @param key
	 * @param newValue
	 */
	public void updateValue(K key, V newValue) {
		wl.lock();
		if (!allowDup) {
			Entry<K, V> entry = findEntry(key, false);
			if (entry != null) {
				entry.value = newValue;
			}
		} else {
			List<Entry<K, V>> entryList = findEntry(key, key, 0, 0, false);
			for (Entry<K, V> entry : entryList) {
				entry.value = newValue;
			}
		}
		wl.unlock();
	}

	/**
	 * 匹配key+value 更新所有记录value
	 * 
	 * @param key
	 * @param value
	 * @param newValue
	 */
	public void updateValue(K key, K value, V newValue) {
		wl.lock();
		List<Entry<K, V>> entryList = findEntry(key, key, 0, 0, false);
		for (Entry<K, V> entry : entryList) {
			if (entry.value.equals(value)) {
				entry.value = newValue;
			}
		}
		wl.unlock();
	}

	/**
	 * 等价于delete(key)+insert(key, value)
	 * 
	 * @param key
	 * @param value
	 */
	public void update(K key, V value) {
		wl.lock();
		_delete(key);
		_insert(key, value);
		wl.unlock();
	}

	/**
	 * 匹配Key，删除所有记录
	 * 
	 * @param key
	 */
	public void delete(K key) {
		wl.lock();
		_delete(key);
		wl.unlock();
	}

	/**
	 * 范围匹配Key in [min,max]，刪除所有记录
	 * 
	 * @param min
	 * @param max
	 */
	public void delete(K min, K max) {
		wl.lock();
		List<Entry<K, V>> entryList = findEntry(min, max, 0, 0, true);
		for (Entry<K, V> entry : entryList) {
			_delete(entry.key);
		}
		wl.unlock();
	}

	/**
	 * 匹配Key，返回是否有记录
	 * 
	 * @param k
	 * @return
	 */
	protected boolean existsEntry(K k) {
		int size = findEntry(k, k, 0, 1, false).size();
		return size > 0;
	}

	/**
	 * 匹配Key，删除第一条记录
	 * 
	 * @param key
	 */
	protected void deleteFirst(K key) {
		Node<K, V> node = root;
		if (node.len == 1 && !node.leaf) {
			Node<K, V> ln = node.childs[0];
			Node<K, V> rn = node.childs[1];
			if (ln.len == degree - 1 && rn.len == degree - 1) {
				merge(node, 0, ln, rn);
				root = ln;
			}
		}
		delete(root, key);
	}

	/**
	 * 分配一个结点
	 * 
	 * @return
	 */
	protected Node<K, V> allocNode() {
		Node<K, V> n = new Node<K, V>(degree);
		return n;
	}

	/**
	 * 分裂满节点
	 * 
	 * @param parent
	 *            父节点
	 * @param pos
	 *            要分裂的满节点在父节点的位置
	 * @param node
	 *            要分裂的节点
	 */
	protected void split(Node<K, V> parent, int pos, Node<K, V> node) {
		// 分配新节点
		Node<K, V> newNode = allocNode();

		// leaf属性继承分裂节点
		newNode.leaf = node.leaf;

		// 将分裂节点的右边t-1个key复制到新节点，分裂节点留下左边的t个
		for (int i = 0; i < degree - 1; i++) {
			newNode.entris[i].asign(node.entris[i + degree].key, node.entris[i
					+ degree].value, newNode, i);
		}

		// 如果是非叶子节点，则将分裂节点右边的子节点也复制到新节点
		if (!newNode.leaf) {
			for (int i = 0; i < degree; i++) {
				newNode.setChild(i, node.childs[i + degree]);
			}
		}

		// 更新节点的key长度
		newNode.len = degree - 1;
		node.len = degree - 1;

		/* 将分裂节点的entry[degree]提为父节点增加entry，并且将新节点作为其右子节点 */
		// 从父节点中留出entry[degree]的位置
		for (int i = parent.len; i > pos; i--) {
			parent.entris[i].asign(parent.entris[i - 1].key,
					parent.entris[i - 1].value, parent, i);
			parent.setChild(i + 1, parent.childs[i]);
		}

		// 将分裂节点的entry[degree]移到父节点
		parent.entris[pos].asign(node.entris[degree - 1].key,
				node.entris[degree - 1].value, parent, pos);
		// 插入到父节点的child[degree]位置
		parent.setChild(pos + 1, newNode);
		// 更新父节点的key长度
		parent.len++;
	}

	/**
	 * 查找Key
	 * 
	 * @param key
	 * @return
	 */
	protected Entry<K, V> findEntry(K key, boolean copy) {
		List<Entry<K, V>> entryList = findEntry(key, key, 0, 1, copy);
		if (entryList.size() == 0) {
			return null;
		}
		return entryList.get(0);
	}

	/**
	 * 查找Key
	 * 
	 * @param key
	 * @return
	 */
	protected List<Entry<K, V>> findEntry(K min, K max, int offset, int limit,
			boolean copy) {
		List<Entry<K, V>> result = new ArrayList<Entry<K, V>>();
		Node<K, V> n = root;

		int pos = -1;
		// 先找到大于或等于min的最左entry
		while (!n.leaf) {
			pos = n.findFirstGe(min);
			n = n.childs[pos];
		}

		// 找entry
		pos = n.findFirstGe(min);
		Entry<K, V> entry;
		if (pos == n.len) {
			// 如果为根节点，且跟节点为空
			if (n == root && pos == 0) {
				return result;
			}
			// 叶子节点无符合结果，找最右节点的后继
			entry = n.entris[pos - 1];
			entry = next(entry);
		} else {
			entry = n.entris[pos];
		}

		// 找到了最左位置，前序遍历，直到key>max或者result的size大于limit
		int off = 0;
		int counter = 0;
		while ((counter < offset + limit || limit == 0) && entry != null) {
			if (max.compareTo(entry.key) < 0) {
				break;
			}
			if (off >= offset && (counter < limit || limit == 0)) {
				if (copy) {
					result.add(entry.clone());
				} else {
					result.add(entry);
				}
				counter++;
				if (limit > 0 && counter >= limit) {
					break;
				}
			}
			off++;
			entry = next(entry);
		}
		return result;

	}

	/**
	 * entry的后继
	 * 
	 * @param entry
	 * @return
	 */
	protected Entry<K, V> next(Entry<K, V> entry) {
		// entry是leaf
		if (entry.node.leaf) {
			// 不是最右entry
			if (entry.pos != entry.node.len - 1) {
				return entry.node.entris[entry.pos + 1];
			} else {
				// 是最右的entry
				Node<K, V> p = entry.node.parent;
				int pos = entry.node.pos;// 节点所在父节点中的位置
				while (p != null && p.len == pos) {
					// 如果p.childs[pos]不存在，则向上遍历
					pos = p.pos;
					p = p.parent;
				}
				if (p == null) {
					return null;
				}
				return p.entris[pos];
			}
		} else {
			// entry不是leaf
			// 找其右子树的最左节点
			Node<K, V> left = left(entry.node.childs[entry.pos + 1]);
			return left.entris[0];
		}
	}

	/**
	 * 插入非空根节点子树
	 * 
	 * @param n
	 * @param k
	 * @param v
	 */
	protected void insert(Node<K, V> n, K k, V v) {
		// 如果是叶子节点，则直接将key插入到节点的对应位置即可
		if (n.leaf) {
			int i = n.len - 1;
			while (i >= 0 && n.entris[i].key.compareTo(k) > 0) {
				n.entris[i + 1].asign(n.entris[i].key, n.entris[i].value, n,
						i + 1);
				i--;
			}
			i++;
			n.entris[i].asign(k, v, n, i);
			n.len++;
			return;
		}

		/* 如果是非叶子节点 */
		// 找到其对应的子树
		int i = n.findFirstＧt(k);
		Node<K, V> c = n.childs[i];// 要插入的子树

		// 如果子树根节点为满，分裂
		if (c.full()) {
			split(n, i, c);
			if (k.compareTo(n.entris[i].key) > 0) {
				i++;
			}
		}

		// 递归插入子树
		insert(n.childs[i], k, v);
	}

	/**
	 * 返回以node为根节点的子树的最左节点
	 * 
	 * @param node
	 * @return
	 */
	protected Node<K, V> left(Node<K, V> node) {
		Node<K, V> result = null;
		while (node != null) {
			result = node;
			node = node.childs[0];
		}
		return result;
	}

	/**
	 * 返回以node为根节点的子树的最右节点
	 * 
	 * @param node
	 * @return
	 */
	protected Node<K, V> right(Node<K, V> node) {
		Node<K, V> result = null;
		while (node != null) {
			result = node;
			node = node.childs[node.len - 1];
		}
		return result;
	}

	/**
	 * 匹配Key，删除所有记录
	 * 
	 * @param key
	 */
	protected void _delete(K key) {
		while (existsEntry(key)) {
			deleteFirst(key);
		}
	}

	/**
	 * 从子树中删除key的记录
	 * 
	 * @param node
	 * @param key
	 */
	protected void delete(Node<K, V> node, K key) {
		int pos = node.findFirstEq(key);
		/* 如果关键词key在node中且node是叶子节点，则从x中删除 */
		if (node.leaf && pos != -1) {
			for (int i = pos; i < node.len - 1; i++) {
				node.entris[i].asign(node.entris[i + 1].key,
						node.entris[i + 1].value, node, i);
			}
			node.len--;
			return;
		}

		/* 如果关键词key在node中，但node是内节点 */
		if (pos != -1) {
			// index之前的字邻居节点至少包含degree个key
			if (node.childs[pos].len >= degree) {
				Node<K, V> right = right(node.childs[pos]);
				K k = right.entris[right.len - 1].key;
				V v = right.entris[0].value;
				if (right != null) {
					delete(node.childs[pos], right.entris[right.len - 1].key);
					node.entris[pos].asign(k, v, node, pos);
				}
			} else if (node.childs[pos + 1].len >= degree) {
				Node<K, V> left = left(node.childs[pos + 1]);
				K k = left.entris[0].key;
				V v = left.entris[0].value;
				if (left != null) {
					delete(node.childs[pos + 1], left.entris[0].key);
					node.entris[pos].asign(k, v, node, pos);
				}
			} else {
				merge(node, pos, node.childs[pos], node.childs[pos + 1]);
				delete(node.childs[pos], key);
			}
			return;
		}

		/* 如果关键词key不在node中 */
		int cpos = node.findFirstＧt(key);
		Node<K, V> cn = node.childs[cpos];
		Node<K, V> lcn = cpos - 1 >= 0 ? node.childs[cpos - 1] : null;
		Node<K, V> rcn = cpos + 1 <= node.len ? node.childs[cpos + 1] : null;

		// 如果cn只包含degree-1个关键词
		if (!node.leaf && cn.len == degree - 1) {
			if ((lcn != null && lcn.len == degree - 1 || lcn == null)
					&& (rcn != null && rcn.len == degree - 1 || rcn == null)) {
				// cn相邻节点都只包含degree-1个子节点
				// 合并cn,rcn
				if (rcn != null) {
					merge(node, cpos, cn, rcn);
				} else {
					merge(node, cpos - 1, lcn, cn);
					cn = lcn;
				}
			} else {
				// cn相邻节点至少一个包含degree+个子节点
				if (lcn != null && lcn.len >= degree) {
					for (int i = degree; i > 0; i--) {
						cn.entris[i].asign(cn.entris[i - 1].key,
								cn.entris[i - 1].value, cn, i);
						cn.setChild(i, cn.childs[i - 1]);
					}
					cn.entris[0].asign(node.entris[cpos - 1].key,
							node.entris[cpos - 1].value, cn, 0);
					cn.setChild(0, lcn.childs[lcn.len - 1]);
					cn.len++;

					node.entris[cpos - 1].asign(lcn.entris[lcn.len - 1].key,
							lcn.entris[lcn.len - 1].value, node, cpos - 1);

					lcn.len--;

				} else {
					cn.entris[cn.len].asign(node.entris[cpos].key,
							node.entris[cpos].value, cn, cn.len);
					cn.setChild(cn.len + 1, rcn.childs[0]);
					cn.len++;

					node.entris[cpos].asign(rcn.entris[0].key,
							rcn.entris[0].value, node, cpos);

					for (int i = 0; i < rcn.len - 1; i++) {
						rcn.entris[i].asign(rcn.entris[i + 1].key,
								rcn.entris[i + 1].value, rcn, i);
					}

					for (int i = 0; i < rcn.len; i++) {
						rcn.setChild(i, rcn.childs[i + 1]);
					}
					rcn.len--;

				}
			}
		}

		// 递归
		if (cn != null) {
			delete(cn, key);
		}
	}

	/**
	 * 合并 parent的key+rn的key合并到ln，rn的最左key移到parent
	 * 
	 * @param parent
	 * @param pos
	 * @param ln
	 * @param rn
	 */
	protected void merge(Node<K, V> parent, int pos, Node<K, V> ln,
			Node<K, V> rn) {
		// 合并要删除的Ｋ节点到左子节点
		ln.entris[degree - 1].asign(parent.entris[pos].key,
				parent.entris[pos].value, ln, degree - 1);

		// 合并右子节点到左子节点
		for (int i = degree; i < 2 * degree - 1; i++) {
			ln.entris[i].asign(rn.entris[i - degree].key,
					rn.entris[i - degree].value, ln, i);
		}
		if (!ln.leaf) {
			for (int i = degree; i < 2 * degree; i++) {
				ln.setChild(i, rn.childs[i - degree]);
			}
		}
		ln.len = 2 * degree - 1;

		// 从父节点删除entris[key]并整理父节点
		for (int i = pos; i < parent.len - 1; i++) {
			parent.entris[i].asign(parent.entris[i + 1].key,
					parent.entris[i + 1].value, parent, i);
		}
		for (int i = pos + 1; i < parent.len; i++) {
			parent.setChild(i, parent.childs[i + 1]);
		}
		parent.len--;
	}

	@Override
	public String toString() {
		return root.toString();
	}

	private static class Entry<K extends Comparable<K>, V> {
		Node<K, V> node;
		K key;
		V value;
		int pos;

		public Entry(K k, V v, Node<K, V> n, int i) {
			key = k;
			value = v;
			node = n;
			pos = i;
		}

		public void asign(K k, V v, Node<K, V> n, int i) {
			key = k;
			value = v;
			node = n;
			// pos = i;//entry的pos是固定的
		}

		@Override
		public String toString() {
			return "<" + key + "," + value + ">";
		}

		@Override
		public Entry<K, V> clone() {
			return new Entry<K, V>(key, value, node, pos);
		}
	}

	private static class Node<K extends Comparable<K>, V> {
		Node<K, V> parent;
		Node<K, V>[] childs;
		Entry<K, V>[] entris;
		int degree;
		int len;
		int pos;
		boolean leaf;

		@SuppressWarnings("unchecked")
		public Node(int d) {
			degree = d;
			childs = new Node[2 * degree];
			entris = new Entry[2 * degree - 1];

			for (int i = 0; i < entris.length; i++) {
				entris[i] = new Entry<K, V>(null, null, this, i);
			}
		}

		public void setChild(int i, Node<K, V> n) {
			if (n != null) {
				n.parent = this;
				n.pos = i;
			}
			childs[i] = n;
		}

		/**
		 * 是否满节点
		 * 
		 * @return
		 */
		public boolean full() {
			return len >= degree * 2 - 1;
		}

		/**
		 * 返回key第一次出现的位置 不存在返回-1
		 * 
		 * @param key
		 * @return
		 */
		public int findFirstEq(K key) {
			for (int i = 0; i < len; i++) {
				if (entris[i].key.compareTo(key) == 0) {
					return i;
				}
			}
			return -1;
		}

		public int findFirstＧt(K key) {
			int i = 0;
			for (i = 0; i < len; i++) {
				if (entris[i].key.compareTo(key) > 0) {
					break;
				}
			}
			return i;
		}

		public int findFirstGe(K key) {
			int i = 0;
			for (i = 0; i < len; i++) {
				if (entris[i].key.compareTo(key) >= 0) {
					break;
				}
			}
			return i;
		}

		@Override
		public String toString() {
			return toString(0);
		}

		public String toString(int indent) {
			String indentStr = "";
			for (int i = 0; i < indent; i++) {
				indentStr += " ";
			}

			StringBuilder sb = new StringBuilder();
			sb.append(indentStr + "<");
			for (int i = 0; i < len; i++) {
				sb.append(entris[i].key);
				if (i < len - 1) {
					sb.append(",");
				}
			}
			sb.append(">\n");
			if (!leaf) {
				for (int i = 0; i <= len; i++) {
					sb.append(childs[i].toString(indent + 2));
				}

			}
			return sb.toString();
		}
	}
}
